EE364A Lecture 3 and Lecture 4

课程主页：https://see.stanford.edu/Course/EE364A

这次回顾凸优化第三，第四讲，这部分介绍了凸函数的概念。

Lecture 3 and Lecture 4 Convex functions

定义

$f : \mathbf{R}^{n} \rightarrow \mathbf{R}$是凸函数，如果$\operatorname{dom} f$是凸集，并且

$$f(\theta x+(1-\theta) y) \leq \theta f(x)+(1-\theta) f(y)$$

对任意$x, y \in \operatorname{dom} f, 0 \leq \theta \leq 1$都成立，图示如下

• $f$是凹的，如果$-f$是凸的

• $f$是严格凸的，如果$\operatorname{dom} f$是凸的，并且

  $$f(\theta x+(1-\theta) y)<\theta f(x)+(1-\theta) f(y)$$

  对任意$x, y \in \operatorname{dom} f, x \neq y, 0<\theta<1$

$\mathbf R$上的例子

凸函数：

• 仿射：$a x+b$，其中$a,b$为$\mathbf R$上任意实数
• 指数函数：$e^{a x}$，其中$a$为$\mathbf R$上任意实数
• 幂函数：定义在$\mathbf{R}_{++}$上的$x^{\alpha}$，其中$\alpha \ge 1$或$\alpha \le 0$
• 绝对值函数的幂：$|x|^{p}, p \ge 1 $
• 负熵：定义在$\mathbf{R}_{++}$的$x \log x$

凹函数：

• 仿射：$a x+b$，其中$a,b$为$\mathbf R$上任意实数
• 幂函数：定义在$\mathbf{R}_{++}$上的$x^{\alpha}$，$0\le \alpha \le 1$
• 对数函数：定义在$\mathbf{R}_{++}$的$ \log x$

$\mathbf{R}^{n}$和$\mathbf{R}^{m \times n}$上的例子

仿射函数既是凸的又是凹的；所有的范数都是凸的。

$\mathbf{R}^{n}$上的例子

• 仿射函数：$f(x)=a^{T} x+b$
• 范数：$|x|_{p}=\left(\sum_{i=1}^{n}\left|x_{i}\right|^{p}\right)^{1 / p} , p \geq 1$，$|x|_{\infty}=\max _{k}\left|x_{k}\right|$

$\mathbf{R}^{m \times n}$上的例子（$m\times n$）

• 仿射函数

  $$f(X)=\operatorname{tr}\left(A^{T} X\right)+b=\sum_{i=1}^{m} \sum_{j=1}^{n} A_{i j} X_{i j}+b$$

• 谱范数（最大奇异值）

  $$f(X)=\|X\|_{2}=\sigma_{\max }(X)=\left(\lambda_{\max }\left(X^{T} X\right)\right)^{1 / 2}$$

将凸函数限制为直线

$f : \mathbf{R}^{n} \rightarrow \mathbf{R}$是凸（凹）函数当且仅当函数$g : \mathbf{R} \rightarrow \mathbf{R}$，

$$g(t)=f(x+t v), \quad \operatorname{dom} g=\{t | x+t v \in \operatorname{dom} f\}$$

对任意$x \in \operatorname{dom} f,v \in \mathbf{R}^{n}$，关于$t$是凸（凹）函数。

例子：$f : \mathrm{S}^{n} \rightarrow \mathrm{R}$，其中

$$f(X)=\log \operatorname{det} X, \operatorname{dom} X=\mathbf{S}_{++}^{n}$$

应用上述定理得到

$$\begin{aligned} g(t)=\log \operatorname{det}(X+t V) &=\log \operatorname{det} X+\log \operatorname{det}\left(I+t X^{-1 / 2} V X^{-1 / 2}\right) \\ &=\log \operatorname{det} X+\sum_{i=1}^{n} \log \left(1+t \lambda_{i}\right) \end{aligned}$$

其中$\lambda_i $是$X^{-1 / 2} V X^{-1 / 2}$的特征值。

因为$g$关于$t$是凹函数；因此$f$是凹函数。

拓展值延伸

$f$的拓展值延伸$\tilde f$为

$$\tilde{f}(x)=f(x), \quad x \in \operatorname{dom} f, \quad \tilde{f}(x)=\infty, \quad x \notin \operatorname{dom} f$$

拓展值延伸可以简化记号；例如，凸函数的条件可以简化为

$$0 \leq \theta \leq 1 \Longrightarrow \tilde{f}(\theta x+(1-\theta) y) \leq \theta \tilde{f}(x)+(1-\theta) \tilde{f}(y)$$

意味着

• $\operatorname{dom} f$是凸集

• 对$x, y\in \operatorname{dom} f$，

  $$0 \leq \theta \leq 1 \quad \Longrightarrow \quad f(\theta x+(1-\theta) y) \leq \theta f(x)+(1-\theta) f(y)$$

一阶条件

假设$f$可微，$\operatorname{dom} f$是开集，梯度

$$\nabla f(x)=\left(\frac{\partial f(x)}{\partial x_{1} }, \frac{\partial f(x)}{\partial x_{2} }, \ldots, \frac{\partial f(x)}{\partial x_{n} }\right)$$

对任意$x \in \operatorname{dom} f$都存在。

凸函数的一阶判别条件为：

$$f(y) \geq f(x)+\nabla f(x)^{T}(y-x) \quad \text { for all } x, y \in \operatorname{dom} f$$

$f$的一阶近似是全局的下界估计。

二阶条件

$f$二阶可微，$\operatorname{dom} f$是开集，$\nabla^{2} f(x) \in \mathbf{S}^{n}$对每个$x \in \operatorname{dom} f$都存在，其中

$$\nabla^{2} f(x)_{i j}=\frac{\partial^{2} f(x)}{\partial x_{i} \partial x_{j} }, \quad i, j=1, \ldots, n$$

凸函数的二阶判别条件为：

• $f$为凸函数当且仅当

  $$\nabla^{2} f(x) \succeq 0 \quad \text { for all } x \in \operatorname{dom} f$$

• 如果对所有$x \in \operatorname{dom} f$，$\nabla^{2} f(x) \succ 0$，那么$f$严格凸

例子

二次函数：$f(x)=(1 / 2) x^{T} P x+q^{T} x+r$，其中$P \in \mathbf{S}^{n}$

$$\nabla f(x)=P x+q, \quad \nabla^{2} f(x)=P$$

如果$P \succeq 0$，那么该函数为凸函数。

最小二乘目标函数：$f(x)=|A x-b|_{2}^{2}$

$$\nabla f(x)=2 A^{T}(A x-b), \quad \nabla^{2} f(x)=2 A^{T} A$$

显然该函数为凸函数。

二次-线性分式函数：$f(x, y)=x^{2} / y$

$$\nabla^{2} f(x, y)=\frac{2}{y^{3} }\left[\begin{array}{c}{y} \\ {-x}\end{array}\right]\left[\begin{array}{c}{y} \\ {-x}\end{array}\right]^{T} \succeq 0$$

对$y>0$是凸函数。

指数和的对数：$f(x)=\log \sum_{k=1}^{n} \exp x_{k}$是凸函数

$$\nabla^{2} f(x)=\frac{1}{1^{T} z} \operatorname{diag}(z)-\frac{1}{\left(\mathbf{1}^{T} z\right)^{2} } z z^{T} \quad\left(z_{k}=\exp x_{k}\right)$$

下面证明上述矩阵半正定，即对于所有$v$，$v^{T} \nabla^{2} f(x) v \geq 0$：

$$v^{T} \nabla^{2} f(x) v=\frac{\left(\sum_{k} z_{k} v_{k}^{2}\right)\left(\sum_{k} z_{k}\right)-\left(\sum_{k} v_{k} z_{k}\right)^{2} }{\left(\sum_{k} z_{k}\right)^{2} } \geq 0$$

其中不等号利用了柯西不等式。

几何平均：定义在$\mathbf{R}_{++}^{n}$上的$f(x)=\left(\prod_{k=1}^{n} x_{k}\right)^{1 / n}$是凹函数

上镜图和下水平集

$f : \mathbf{R}^{n} \rightarrow \mathbf{R}$的$\alpha - $下水平集定义为

$$C_{\alpha}=\{x \in \operatorname{dom} f | f(x) \leq \alpha\}$$

凸函数的下水平集为凸集（反之不成立）

$f : \mathbf{R}^{n} \rightarrow \mathbf{R}$的上镜图定义为

$$\operatorname{epi} f=\left\{(x, t) \in \mathbf{R}^{n+1} | x \in \operatorname{dom} f, f(x) \leq t\right\}$$

$f$是凸函数当且仅当$\operatorname{epi} f$是凸集

Jensen不等式

基本不等式：如果$f$是凸集，那么对于$0\le \theta \le1$，

$$f(\theta x+(1-\theta) y) \leq \theta f(x)+(1-\theta) f(y)$$

推广：如果$f$是凸集，那么对任意随机变量$z$

$$f(\mathbf{E} z) \leq \mathbf{E} f(z)$$

基本不等式是推广的特殊情形：

$$\operatorname{prob}(z=x)=\theta, \quad \operatorname{prob}(z=y)=1-\theta$$

保凸运算

非负加权和以及复合仿射函数

非负相乘：若果$f$是凸函数，$\alpha \ge 0$，那么$\alpha f $是凸函数

和：如果$f_1,f_2$是凸函数，那么$f_1 +f_2$是凸函数（推广到无限和以及积分）

仿射函数复合：如果$f$是凸函数，那么$f(Ax+b)$是凸函数

例子：

• 对数函数和仿射函数复合

  $$f(x)=-\sum_{i=1}^{m} \log \left(b_{i}-a_{i}^{T} x\right), \quad \operatorname{dom} f=\left\{x | a_{i}^{T} x<b_{i}, i=1, \ldots, m\right\}$$

• 仿射函数的范数

  $$f(x)=\|A x+b\|$$

逐点最大值

如果$f_{1}, \ldots, f_{m}$是凸函数，那么$f(x)=\max \left\{f_{1}(x), \ldots, f_{m}(x)\right\}$是凸函数

例子：

• $f(x)=\max _{i=1, \ldots, m}\left(a_{i}^{T} x+b_{i}\right)$是凸函数

• $x \in \mathbf{R}^{n}$的$r$个最大分量：

  $$f(x)=x_{[1]}+x_{[2]}+\cdots+x_{[r]}$$

  证明：

  $$f(x)=\max \left\{x_{i_{1} }+x_{i_{2} }+\cdots+x_{i_{r} } | 1 \leq i_{1}<i_{2}<\cdots<i_{r} \leq n\right\}$$

逐点上确界

如果对每个$y \in \mathcal{A}$，$f(x,y)$关于$x$是凸函数，那么

$$g(x)=\sup _{y \in \mathcal{A} } f(x, y)$$

是凸函数。

例子：

• $S_{C}(x)=\sup _{y \in C} y^{T} x$是凸函数

• $f(x)=\sup _{y \in C}|x-y|$

• 对称矩阵的最大值$X \in \mathbf{S}^{n}$

  $$\lambda_{\max }(X)=\sup _{\|y\|_{2}=1} y^{T} X y$$

标量函数复合

考虑$g : \mathbf{R}^{n} \rightarrow \mathbf{R}$以及$h : \mathbf{R} \rightarrow \mathbf{R}$的复合：

$$f(x)=h(g(x))$$

$f$是凸函数，如果

• $g$是凸函数，$h$是凸函数，$\tilde h$非减
• $g$是凹函数，$h$是凸函数，$\tilde h$非增

证明：考虑$n=1$的情形，

$$f^{\prime \prime}(x)=h^{\prime \prime}(g(x)) g^{\prime}(x)^{2}+h^{\prime}(g(x)) g^{\prime \prime}(x)$$

例子：

• 如果$g$是凸函数，那么$\exp g(x)$是凸函数
• 如果$g$是正凹函数，那么$1/ g(x)$是凸函数

向量复合

考虑$g : \mathbf{R}^{n} \rightarrow \mathbf{R}^k$以及$h : \mathbf{R}^k \rightarrow \mathbf{R}$的复合：

$$f(x)=h(g(x))=h\left(g_{1}(x), g_{2}(x), \ldots, g_{k}(x)\right)$$

$f$是凸函数，如果

• $g_i$是凸函数，$h$是凸函数，$\tilde h$关于每个分量非减
• $g_i $是凹函数，$h$是凸函数，$\tilde h $关于每个分量非增

证明：考虑$n=1$的情形，

$$f^{\prime \prime}(x)=g^{\prime}(x)^{T} \nabla^{2} h(g(x)) g^{\prime}(x)+\nabla h(g(x))^{T} g^{\prime \prime}(x)$$

例子：

• $\sum_{i=1}^{m} \log g_{i}(x)$是凹函数，如果$g_i$是正凹函数
• $\log \sum_{i=1}^{m} \exp g_{i}(x)$是凸函数，如果$g_i$是凸函数

最小化

$f(x,y)$关于$(x,y)$是凸函数，并且$C$是凸集，那么

$$g(x)=\inf _{y \in C} f(x, y)$$

是凸函数。

例子

• $f(x, y)=x^{T} A x+2 x^{T} B y+y^{T} C y$，其中

  $$\left[\begin{array}{cc}{A} & {B} \\ {B^{T} } & {C}\end{array}\right] \succeq 0, \quad C \succ 0$$

  关于$y$最小化得到

  $$g(x)=\inf _{y} f(x, y)=x^{T}\left(A-B C^{-1} B^{T}\right) x$$

• 如果$S$是凸集，那么

  $$\operatorname{dist}(x, S)=\inf _{y \in S}\|x-y\|$$

  是凸集

透视函数

$f : \mathbf{R}^{n} \rightarrow \mathbf{R}$的透视函数为$g : \mathbf{R}^{n} \times \mathbf{R} \rightarrow \mathbf{R}$，其中

$$g(x, t)=t f(x / t), \quad \operatorname{dom} g=\{(x, t) | x / t \in \operatorname{dom} f, t>0\}$$

如果$f$是凸函数，那么$g$是凸函数。

例子：

• $f(x)=x^T x$是凸函数，所以$g(x, t)=x^{T} x / t,t>0$是凸函数

• 负对数函数$f(x)=-\log x$是凸函数；因此相对熵$g(x, t)=t \log t-t \log x$是$\mathbf{R}_{++}^{2}$上凸函数

• $f$是凸函数，那么

  $$g(x)=\left(c^{T} x+d\right) f\left((A x+b) /\left(c^{T} x+d\right)\right)$$

  是凸函数，其中定义域为

  $$\left\{x | c^{T} x+d>0,(A x+b) /\left(c^{T} x+d\right) \in \operatorname{dom} f\right\}$$

共轭函数

$f$的共轭为

$$f^{*}(y)=\sup _{x \in \operatorname{dom} f}\left(y^{T} x-f(x)\right)$$

关于共轭有如下性质

• $f^*$是凸函数

例子：

• 负对数函数$f(x)=-\log x$

  $$\begin{aligned} f^{*}(y) &=\sup _{x>0}(x y+\log x) \\ &=\left\{\begin{array}{cc}{-1-\log (-y)} & {y<0} \\ {\infty} & {\text { otherwise } }\end{array}\right.\end{aligned}$$

• 严格二次凸函数$f(x)=(1 / 2) x^{T} Q x,Q \in \mathbf{S}_{++}^{n} $

  $$\begin{aligned} f^{*}(y) &=\sup _{x}\left(y^{T} x-(1 / 2) x^{T} Q x\right) \\ &=\frac{1}{2} y^{T} Q^{-1} y \end{aligned}$$

拟凸函数

$f : \mathbf{R}^{n} \rightarrow \mathbf{R}$是拟凸函数，如果$\operatorname{dom} f$是凸集，并且下水平集对任意$\alpha $是凸集

$$S_{\alpha}=\{x \in \operatorname{dom} f | f(x) \leq \alpha\}$$

• $f$是拟凹，如果$-f$是拟凸
• $f$是拟线性，如果$f$是拟凸并且拟凹

例子

• $\sqrt{|x|}$是$\mathbf R $上拟凸函数

• $\operatorname{ceil}(x)=\inf \{z \in \mathbf{Z} | z \geq x\}$是拟线性

• $\log x$是$\mathbf{R}_{++}$上拟线性

• $f\left(x_{1}, x_{2}\right)=x_{1} x_{2}$是$\mathbf{R}_{++}^{2}$上拟凹函数

• 线性分式函数

  $$f(x)=\frac{a^{T} x+b}{c^{T} x+d}, \quad \text { dom } f=\left\{x | c^{T} x+d>0\right\}$$

  是拟线性

• 距离比

  $$f(x)=\frac{\|x-a\|_{2} }{\|x-b\|_{2} }, \quad \operatorname{dom} f=\left\{x |\|x-a\|_{2} \leq\|x-b\|_{2}\right\}$$

  是拟凸函数

拟凸函数的性质

调整的Jenson不等式：对于拟凸函数$f$

$$0 \leq \theta \leq 1 \quad \Longrightarrow \quad f(\theta x+(1-\theta) y) \leq \max \{f(x), f(y)\}$$

一阶条件：可微$f$关于凸定义域是拟凸函数当且仅当

$$f(y) \leq f(x) \quad \Longrightarrow \quad \nabla f(x)^{T}(y-x) \leq 0$$

注意，拟凸函数的和不一定是拟凸函数

对数凸以及对数凹函数

$f$是对数凹函数，如果$\log f$是凹函数：

$$f(\theta x+(1-\theta) y) \geq f(x)^{\theta} f(y)^{1-\theta} \quad \text { for } 0 \leq \theta \leq 1$$

$f$是对数凸函数，如果$\log f$是对数凸

• $\mathbf{R}_{++}$上的$x^{a}$是对数凸函数，如果$a\le 0$；是对数凹函数，如果$\alpha \ge 0$

• 正态分布是对数凹函数

  $$f(x)=\frac{1}{\sqrt{(2 \pi)^{n} \operatorname{det} \Sigma} } e^{-\frac{1}{2}(x-\overline{x})^{T} \Sigma^{-1}(x-\overline{x})}$$

• 正态分布的累计分布函数是对数凹函数

  $$\Phi(x)=\frac{1}{\sqrt{2 \pi} } \int_{-\infty}^{x} e^{-u^{2} / 2} d u$$

对数凹函数的性质

• 定义域为凸集的二阶可微的$f$为对数凹函数当且仅当对任意$x \in \operatorname{dom} f$，

  $$f(x) \nabla^{2} f(x) \preceq \nabla f(x) \nabla f(x)^{T}$$

• 对数凹函数的乘积是对数凹函数

• 对数凹函数的和不总是对数凹函数

• 积分：如果$f : \mathbf{R}^{n} \times \mathbf{R}^{m} \rightarrow \mathbf{R}$是对数凹函数，那么

  $$g(x)=\int f(x, y) d y$$

  是对数凹函数

积分性质的结果

• 如果$f,g$是对数凹函数，那么

  $$(f * g)(x)=\int f(x-y) g(y) d y$$

  是对数凹函数

• $C \subseteq \mathrm{R}^{n}$是凸集，$y$是pdf为对数凹函数的随机变量，那么

  $$f(x)=\operatorname{prob}(x+y \in C)$$

  是对数凹函数

  证明：定义

  $$f(x)=\int g(x+y) p(y) d y, \quad g(u)=\left\{\begin{array}{ll}{1} & {u \in C} \\ {0} & {u \notin C}\end{array}\right.$$

  其中$p$为$y$的pdf

关于广义不等式的凸性

$f : \mathbf{R}^{n} \rightarrow \mathbf{R}^{m}$是$K$凸，如果$\operatorname{dom} f$是凸集，并且

$$f(\theta x+(1-\theta) y) \preceq_{K} \theta f(x)+(1-\theta) f(y)$$

对任意$x, y \in \operatorname{dom} f, 0 \leq \theta \leq 1$都成立，图示如下

例子：

$$f : \mathrm{S}^{m} \rightarrow \mathrm{S}^{m}, f(X)=X^{2}为 \mathrm{S}_{+}^{m}凸$$

证明：固定$z \in \mathbf{R}^{m}$，$z^{T} X^{2} z=|X z|_{2}^{2}$关于$X$是凸集，即

$$z^{T}(\theta X+(1-\theta) Y)^{2} z \leq \theta z^{T} X^{2} z+(1-\theta) z^{T} Y^{2} z$$

对于$X, Y \in \mathbf{S}^{m}, 0 \leq \theta \leq 1$成立。

因此

$$(\theta X+(1-\theta) Y)^{2} \preceq \theta X^{2}+(1-\theta) Y^{2}$$